高级算法之Balls into Bins

Balls into Bins

• 背景: 将$m$个球独立均匀随机地扔进$n$个盒子, 等价于随机映射$f:[m]\to[n]$.

1 生日问题

• 问题: $m$个学生生日独立随机均匀分布于一年365天. 求没有两人同一天生日的概率

  • 等价于: 将$m$个不同的球扔进365个盒子. 更一般的, 盒子数为$n$.
  • 事件$\epsilon$: 没有盒子里面有多于1个球

• 总共$n^m$中扔法, 其中没有一个盒子有多于1个球的扔法有$\binom{n}{m}m!$种, 因此

  $$Pr[\epsilon]=\frac{\binom{n}{m}m!}{n^m}=\frac{n!}{n^m(n-m)!}=\prod_{k=1}^{m-1}(1-\frac{k}{n})$$

• 另一解释: 一个学生按顺序来算

• 根据泰勒展开$e^{-k/n}\approx1-k/n$, 有

  $$\begin{aligned} \prod_{k=1}^{m-1}(1-\frac{k}{n})&\approx\prod_{k=1}^{m-1}e^{-k/n}\\ &=\exp(-\sum_{k=1}^{m-1}\frac{k}{n})\\ &=e^{-m(m-1)/2n}\\ &\approx e^{-m^2/2n} \end{aligned}$$

• 取$m=\sqrt{2n\ln\frac{1}{\epsilon}}$, 有$Pr[\epsilon]\approx \epsilon$

• 实际上没有两人同一天生日的概率很小

2 Coupon Collector

• 问题: $n$种票, 随机获取. 多少次才能集齐

  • 等价于: 随机扔球进$n$个盒子, 扔多少个才能没有盒子是空的

• 记录扔的次数为$X$, 则$\mathbb E[X]=nH(x)$, $H(x)$是第$n$个调和数

  证明:

  • 记恰好有$i-1$个非空盒子时候, 再扔一个球进非空盒子需要的球数为$X_i$, $X=\sum_{i=1}^nX_i$

  • 恰好有$i-1$个非空盒子时候, 再扔一个球进非空盒子的概率是$p_i=1-\frac{i-1}{n}$

  • $X_i$服从几何分布, $Pr[X_i=k]=(1-p_i)^{k-1}p_i$, $\mathbb E[X_i]=\frac{1}{p_i}=\frac{n}{n-i+1}$

  • $$\begin{aligned} \mathbb E[X]&=\mathbb E[\sum_{i=1}^n X_i]\\ &= \sum_{i=1}^n \mathbb E[X_i]\\ &=\sum_{i=1}^n\frac{n}{n-i+1}\\ &= n\sum_{i=1}^n\frac{1}{i}\\ &=nH(n) \end{aligned}$$

  • $H(n)=\ln n+O(1)$, 因此$\mathbb E[X]=n\ln n+O(n)$

• 对于任意$c>0$, $Pr[X\ge n\ln n+cn]<e^{-c}$

  证明

  • 对于任意盒子$i$, 在扔了$n\ln n+cn$个球之后为空的概率为

    $(1-\frac{1}{n})^{n\ln n+cn}<e^{-(\ln n + c)}=\frac{1}{ne^c}$

  • $Pr[X\ge n\ln n+cn]<n\frac{1}{ne^c}=e^{-c}$

3 Occupancy Problem

• 考虑盒子的装载量, 显然$\mathbb E[X_i]=m/n$

• 因此$\sum_{i=1}^n\mathbb E[X_i]=\mathbb E[\sum_{i=1}^n X_i]=\mathbb E[m]=m$

• 下面考虑最大装载量$\max_{1\le i\le n}X_i$:

  $$Pr[\max_{1\le i\le n} X_i\ge \frac{3\ln n}{\ln\ln n}]<\frac{1}{n}$$

  证明:

  • 对于任意$M$个球, 全都扔进盒子1的概率为$(1/n)^M$, 而$M$个球的选择有$\binom{n}{m}$种

    $$\begin{aligned} Pr[X_1\ge M]&\le \binom{n}{m}\left(\frac{1}{n}\right)^M\\ &=\frac{n!}{M!(n-M)!n^M}\\ &=\frac{1}{M!}\cdot \frac{n(n-1)(n-2)\cdots(n-M+1)}{n^M}\\ &=\frac{1}{M!}\cdot \prod_{i=0}^{M-1}(1-i/n)\\ &\le \frac{1}{M!}\\ &\le\left(\frac{e}{M}\right)^M \end{aligned}$$

    注意这里第一步为$\le$是因为后面的计算方法有计算重复的, 最后一步是因为斯特林近似$M!\approx\sqrt{2\pi M}\left(\frac{M}{e}\right)^M$

  • $$\begin{aligned} Pr[\max_{1\le i\le n}X_i\ge M]&=Pr[(X_1\ge M)\lor(X_2\ge M)\lor\cdots\lor(X_n\ge M)]\\ &\le nPr[X_1\ge M]\\ &\le n\left(\frac{e}{M}\right)^M\\ &=n\left(\frac{e\ln\ln n}{3\ln n}\right)^{\frac{3\ln n}{\ln\ln n}}\\ &<n\left(\frac{\ln\ln n}{\ln n}\right)^{\frac{3\ln n}{\ln\ln n}}\\ &=n \exp(3(\ln\ln\ln n-\ln\ln n)\ln n/\ln\ln n)\\ &=n \exp(-3\ln n+3\ln\ln\ln n\ln n/\ln \ln n)\\ &\le n \exp(-2\ln n)\\ &=n\cdot\frac{1}{n^2}\\ &=\frac{1}{n} \end{aligned}$$

    注意这里倒数第二步的那个$\le$我认为只有在$n$不小的时候成立

• 对于$m=\Omega(n\log n)$, 有大概率最大装载量为$O(m/n)$